It may be desirable to provide security for communications that traverse networks (e.g., public networks). Security for gateways that communicate with each other using public networks may include encrypting data traffic between gateways to prevent snooping and/or inserting malicious material into the data traffic (e.g., spoofing). Encrypting data may also facilitate verifying the authenticity of a message. Authenticating a message may include verifying that the message was sent by the identified sender. Security between gateways is necessary when utilizing virtual private networks (VPNs) that use mesh networking that traverse public networks.
Traditional encryption embodiments have utilized a single key or single set of keying material for all members (e.g., gateways) of a network. In this simple group-keyed network solution, all gateways install and use the same encryption keys (e.g., keys). One skilled in the art will realize that a key may be used by itself, or with other secret material, to encrypt the message. The simple group-keyed network solution may provide an adequate level of security in a low threat environment because each gateway is trusted to pass the same data to any other gateway. In this configuration, it must be assumed that all gateways are trusted identically. However, a vulnerability may exist. An attacker may simply take over a single gateway and may then eavesdrop on all traffic in the network. Additionally, the attacker may inject packets claiming to be from any of the legitimate gateways.
A single gateway may be compromised, for example, due to poor physical security or poor firewalls. If a single gateway is taken over by an attacker, encryption between all members may be compromised if the network uses the simple group-keyed method where a single key set is distributed to all network members. Thus, simple group-keyed networks do not provide adequate security in a hostile environment.
Pair-wise keying has been implemented in networks in response to the security issues associated with single group-keyed networks. Pair-wise keying may provide a key or pair of keys for each possible connection between gateways. However, when a network includes a large number of nodes/gateways, providing keys for every pair (e.g., pair-wise keying) may become problematic. For a network of one hundred nodes, 100×99 keys are required for pair-wise keying. This requires communicating on the order of 156 kilobytes of memory to handle keys that are 128 bit values. However, as the number of nodes increases, the amount of memory required to store the keys is squared relative to the number of nodes. This is because each possible pairing requires a key. Therefore, it may become impractical, if possible at all, to store all of the keys required for a large mesh network.
A symmetric Key Generation System, or KGS for short, is a system that allows a pair of users to generate a secret pair-wise key using secret data that was issued to the pair of users by a trusted authority. Each user of the KGS receives a different set of data from the authority. The algorithm by which an entity generates a pair-wise key to communicate with another entity takes as an input the secret data of the first user and the identifier of the second user. The identifiers are controlled by the trusted authority. When a user is introduced into the system, that user is issued secret data and a particular identifier by the authority. The KGS itself provides no way to securely communicate the shared secret data between the authority and the users. Instead, there is a secure channel between the authority and the user over which this data is passed.
When two users of the system need to communicate securely, they compute a pair-wise key as follows. The two users employ a process that takes as an input their own secret data and the identity of the other entity with which the pair-wise key is to be shared. The process outputs the pairwise key. This system can be used to generate n(n−1)/2 keys that can be used for pairwise communication between n users. A user can generate, on demand, any of the n−1 keys that that user might need. When using a KGS, the storage used by a user to store the secret data issued to them by the authority is much smaller than n−1 keys.
A KGS is called k-secure if the compromise of k or fewer users does not affect the security of the system. The threshold k is a parameter of the system. It is possible to make a KGS in which each user stores O(k) data, where k is independent of the number n of users of the system. R. Blom described a particular KGS in An Optimal Class of Symmetric Key Generation Systems, Advances in Cryptology: Proceedings of Eurocrypto 84, Lecture Notes in Computer Science. Vol 209, Springer-Verlag, Berlin, 1984, pp. 335-338. In general, an abstract KGS can be considered to be a particular set of processes based on a particular set of algorithms. There is an algorithm that the authority uses to initialize the KGS. This is a random process, and the authority maintains the data generated by this process as a secret. This data is called the KGS authority secret data. There is another algorithm by which the authority computes the secret data to be given to the users. This data is called the KGS user secret data. There is yet another algorithm by which a user computes a pairwise key from their secret data and the identifier of the other user.